"""
归并排序
归并排序采用分治思想，把待排序序列分成N个子序列，子序列排序后，合并两个子序列实现排序
"""
def Merge_Sort(array):
    if len(array) < 2:
        return array
    mid = len(array)//2
    # 左边
    left = Merge_Sort(array[:mid])
    # 右边
    right = Merge_Sort(array[mid:])
    # 合并
    i, j = 0, 0
    res = []
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            res.append(left[i])
            i += 1
        else:
            res.append(right[j])
            j += 1
    # 拼接
    return res + left[i:] + right[j:]

if __name__=="__main__":
    array=[3,2,1,5,5,7,8,3,23,42,42,3,2,1]
    res=Merge_Sort(array)
    print(res)


